#include"heap.h"
void HeapInit(Heap* php)
{
	assert(php);
	php->data = NULL;
	php->size = 0;
	php->capacity = 0;
}
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->data);
	php->size = 0;
	php->capacity = 0;
}
void swap(HeapDataType* pa, HeapDataType* pb)
{
	assert(pa && pb);
	HeapDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void AdjustUp(Heap* php,size_t child)
{
	assert(php);
	assert(php->data);
	size_t parent = (child - 1) / 2;
	while (child>0)
	{
		if (php->data[parent] > php->data[child])
		{
			swap(&(php->data[parent]), &(php->data[child]));
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = (php->capacity == 0) ? 4 : 2 * php->capacity;
		int* tmp = realloc(php->data, sizeof(int) * newcapacity);
		assert(tmp);
		php->data = tmp;
		php->capacity = newcapacity;
	}
	php->data[php->size++] = x;
	AdjustUp(php,php->size-1);
}
void HeapPrint(Heap* php)
{
	assert(php);
	assert(php->data);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->data[i]);
	}
	printf("\n");
}
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	swap(&(php->data[0]), &(php->data[php->size - 1]));
	php->size--;
	if (php->size > 0)
	{
		AdjustDown(php, 0);
	}
}
void AdjustDown(Heap* php, size_t root)
{
	assert(php);
	assert(php->size > 0);
	size_t child = 2 * root + 1;
	while (child < php->size)
	{
		if ((child + 1 < php->size) && (php->data[child] > php->data[child + 1]))
		{
			child++;
		}
		if (php->data[root] > php->data[child])
		{
			swap(&(php->data[root]), &(php->data[child]));
			root = child;
			child = root * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}
size_t HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}
HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->data[0];
}